package 剑指offer;

import common.TreeNode;

/**
 * @author zhangmin
 * @create 2021-11-28 13:35
 *
 * 搜索与回溯算法（中等）
 */
public class day18_551_552 {

    /**===========================================================================================================================
     * 剑指 Offer 55 - I. 二叉树的深度
     * 输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
     * 1、递归
     * 2、创建队列，记录每一层的元素
     * */
    public int maxDepth(TreeNode root) {
        if(root==null) return 0;
        return 1+ Math.max(maxDepth(root.left),maxDepth(root.right));
    }



    /**===========================================================================================================================
     * 剑指 Offer 55 - II. 平衡二叉树
     * 输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
     * 1、前序遍历，对每个节点判断左右子树的深度  --自顶向下
     * 2、后续遍历，先判断左右子树是否平衡， 再判断当前节点是否平衡--自底向上
     * */
    public boolean isBalanced1(TreeNode root) {
        if (root==null) return true;
        int dif=Math.abs(maxDepth(root.left)-maxDepth(root.right));
        if (dif<=1) return isBalanced(root.right)&&isBalanced(root.left);
        else {
            return false;
        }
    }

    public boolean isBalanced(TreeNode root) {
        return depth(root)>=0;
    }
    public int depth(TreeNode root){
        if (root==null) return 0;
        int left=depth(root.left);
        int right=depth(root.right);
        if (left==-1||right==-1||Math.abs(left-right)>1)
            return -1;
        else {
            return Math.max(left,right)+1;
        }
    }
}
